//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// lru_k_replacer.cpp
//
// Identification: src/buffer/lru_k_replacer.cpp
//
// Copyright (c) 2015-2022, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include "buffer/lru_k_replacer.h"
#include "common/exception.h"
namespace bustub {

LRUKReplacer::LRUKReplacer(size_t num_frames, size_t k) : replacer_size_(num_frames), k_(k) {
  // std::cout << "LRUKReplacer(" << num_frames << "," << k << ")" << std::endl;
}

auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool {
  latch_.lock();
  // std::cout << "evict()" << std::endl;
  frame_id_t lru_frame_id = -1;
  size_t earlist_timestamp = SIZE_MAX;
  decltype(fresh_node_list_)::iterator it;
  decltype(fresh_node_list_)::iterator evict_it;
  // select lru node from evictable fresh node
  for (it = fresh_node_list_.begin(); it != fresh_node_list_.end(); ++it) {
    if (it->is_evictable_) {
      /* if(it->history_.back() < earlist_timestamp) {
          earlist_timestamp = it->history_.back();
          lru_frame_id = it->fid_;
          evict_it = it;
      } */
      lru_frame_id = it->fid_;
      evict_it = it;
      break;
    }
  }

  // has find a victim, evict it and return
  if (lru_frame_id != -1) {
    *frame_id = lru_frame_id;
    fresh_node_list_.erase(evict_it);
    curr_size_--;
    latch_.unlock();
    return true;
  }

  // select lru-k node from evictable resident node
  for (it = resident_node_list_.begin(); it != resident_node_list_.end(); ++it) {
    if (it->is_evictable_) {
      BUSTUB_ASSERT(it->history_.size() >= k_,
                    "node with access time less "
                    "than K shouldn't be in resident_node_list!\n");
      auto timestamp_it = it->history_.end();
      for (size_t i = 0; i < k_; ++i) {
        timestamp_it--;
      }
      if (*timestamp_it < earlist_timestamp) {
        earlist_timestamp = *timestamp_it;
        lru_frame_id = it->fid_;
        evict_it = it;
      }
    }
  }

  // has find a victim, evict it and return
  if (lru_frame_id != -1) {
    *frame_id = lru_frame_id;
    resident_node_list_.erase(evict_it);
    curr_size_--;
    latch_.unlock();
    return true;
  }
  latch_.unlock();
  return false;
}

void LRUKReplacer::RecordAccess(frame_id_t frame_id, [[maybe_unused]] AccessType access_type) {
  latch_.lock();
  // std::cout << "RecordAccess(" << frame_id << ")" << std::endl;

  // if frame_id is invalid
  if (frame_id > static_cast<int32_t>(replacer_size_)) {
    latch_.unlock();
    throw Exception(std::string("In func ") + __func__ + ":frame id is invalid");
    return;
  }
  std::list<LRUKNode>::iterator it;
  for (it = fresh_node_list_.begin(); it != fresh_node_list_.end(); ++it) {
    if (it->fid_ == frame_id) {
      break;
    }
  }
  if (it == fresh_node_list_.end()) {
    for (it = resident_node_list_.begin(); it != resident_node_list_.end(); ++it) {
      if (it->fid_ == frame_id) {
        break;
      }
    }
    if (it == resident_node_list_.end()) {
      // assume that overflow record won't happen
      BUSTUB_ASSERT(curr_size_ < replacer_size_, "the replacer has been full already!");
      // create histort for new frame
      CreateNewEntry(frame_id);
      latch_.unlock();
      return;
    }

    it->history_.push_back(current_timestamp_);
    current_timestamp_++;

  } else {
    it->history_.push_back(current_timestamp_);
    current_timestamp_++;
    if (it->history_.size() >= k_) {
      LRUKNode t_node = *it;
      fresh_node_list_.erase(it);
      resident_node_list_.push_back(t_node);
    }
  }

  latch_.unlock();
}

void LRUKReplacer::SetEvictable(frame_id_t frame_id, bool set_evictable) {
  latch_.lock();
  // std::cout << "SetEvictable(" << frame_id << "," << set_evictable << ")" << std::endl;
  for (auto &node : fresh_node_list_) {
    if (node.fid_ == frame_id) {
      if (node.is_evictable_ && !set_evictable) {
        curr_size_--;
      } else if (!node.is_evictable_ && set_evictable) {
        curr_size_++;
      }
      node.is_evictable_ = set_evictable;
      latch_.unlock();
      return;
    }
  }

  for (auto &node : resident_node_list_) {
    if (node.fid_ == frame_id) {
      if (node.is_evictable_ && !set_evictable) {
        curr_size_--;
      } else if (!node.is_evictable_ && set_evictable) {
        curr_size_++;
      }
      node.is_evictable_ = set_evictable;
      latch_.unlock();
      return;
    }
  }

  latch_.unlock();
}

void LRUKReplacer::Remove(frame_id_t frame_id) {
  latch_.lock();
  // std::cout << "Remove(" << frame_id << ")" << std::endl;
  decltype(fresh_node_list_)::iterator it;
  for (it = fresh_node_list_.begin(); it != fresh_node_list_.end(); ++it) {
    if (it->fid_ == frame_id) {
      if (!it->is_evictable_) {
        throw Exception(std::string(__func__) + ": frame given is non-evictable");
      }
      fresh_node_list_.erase(it);
      curr_size_--;
      latch_.unlock();
      return;
    }
  }

  for (it = resident_node_list_.begin(); it != resident_node_list_.end(); ++it) {
    if (it->fid_ == frame_id) {
      if (!it->is_evictable_) {
        throw Exception(std::string(__func__) + ": frame given is non-evictable");
      }
      it = resident_node_list_.erase(it);
      curr_size_--;
    }
  }
  latch_.unlock();
}

auto LRUKReplacer::Size() -> size_t { return curr_size_; }

void LRUKReplacer::CreateNewEntry(frame_id_t frame_id) {
  LRUKNode t_node;
  t_node.fid_ = frame_id;
  t_node.history_.push_back(current_timestamp_);
  fresh_node_list_.push_back(std::move(t_node));
}

}  // namespace bustub
